package _2022.hot100._17_电话号码的字母组合;

import java.util.*;

/**
 * @author： YHSimon
 * @date： 2022-03-29 17:32
 */
public class Solution {


    //递归形式实现回溯 推荐
    public List<String> letterCombination(String digits){
        List<String> combinations = new ArrayList<>();
        if(digits.length()==0){
            return combinations;
        }
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        backtrack(combinations,map,digits,0,new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations,Map<Character,String> map,String digits,int index,StringBuffer combination){
        if(index==digits.length()){
            combinations.add(combination.toString());
        }else{
            char digit=digits.charAt(index);
            String letters=map.get(digit);
            int letterCounter=letters.length();
            for(int i=0;i<letterCounter;i++){
                combination.append(letters.charAt(i));
                backtrack(combinations, map, digits, index+1, combination);
                combination.deleteCharAt(index);
            }
        }
    }


    //1ms  模拟
    public List<String> letterCombinations2(String digits) {
        int len = digits.length();
        if (len < 1) {
            return new ArrayList<>();
        }
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        List<String> res = new ArrayList<>();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            list.add(map.get(digits.charAt(i)));
        }
        StringBuilder sb = new StringBuilder();
        if (list.size() >= 1) {
            for (char c1 : list.get(0).toCharArray()) {
                sb.delete(0, sb.length());
                sb.append(c1);
                if (list.size() >= 2) {
                    for (char c2 : list.get(1).toCharArray()) {
                        sb.delete(1, sb.length());
                        sb.append(c2);
                        if (list.size() >= 3) {
                            for (char c3 : list.get(2).toCharArray()) {
                                sb.delete(2, sb.length());
                                sb.append(c3);
                                if (list.size() >= 4) {
                                    for (char c4 : list.get(3).toCharArray()) {
                                        sb.delete(3, sb.length());
                                        sb.append(c4);
                                        res.add(sb.toString());
                                    }
                                } else {
                                    res.add(sb.toString());
                                }
                            }
                        } else {
                            res.add(sb.toString());
                        }
                    }
                } else {
                    res.add(sb.toString());
                }
            }
        }
        return res;
    }



    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.letterCombinations2("3").toString());
    }
}
